import collections


# 二叉树相关
# 反转二叉树：
def invert_tree(root):
    if not root:
        return None
    tmp = root.left
    root.left = root.right
    root.right = tmp

    invert_tree(root.left)
    invert_tree(root.right)

    return root


# 填充二叉树的右侧指针：leetcode 116
def connect(root):
    # 层序遍历
    if not root:
        return root
    q = collections.deque()
    q.append(root)
    while q:
        tmp = len(q)
        for i in range(tmp):
            cur = q.popleft()
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)
            if i < tmp - 1:
                cur.next = q[0]
    return root

    # # 递归链接
    # def connect_two_node(node1, node2):
    #     if not (node1 or node2):
    #         return
    #     node1.next = node2
    #     connect_two_node(node1.left, node1.right)
    #     connect_two_node(node2.left, node2.right)
    #     connect_two_node(node1.right, node2.left)
    #
    # if not root:
    #     return root
    # connect_two_node(root.left, root.right)
    # return root


# 将二叉树扁平化为链表：
def flatten(root):
    """
    Do not return anything, modify root in-place instead.
    """
    if not root:
        return root
    flatten(root.left)
    flatten(root.right)
    if root.left and root.right:
        # 寻找root.left尾部用的指针
        index = root.left
        # while循环找root.left的尾部
        while index.right:
            index = index.right
        # 进行拼接工作
        index.right = root.right
        root.right = root.left
        root.left = None

    elif not root.right and root.left:
        root.rigth = root.left
        root.left = None


# leetcode 654构造最大二叉树
def constructMaximumBinaryTree(nums):
    if not nums:
        return
    max_index = nums.index(max(nums))
    left = nums[:max_index]
    right = nums[max_index + 1:]
    node = TreeNode(nums[max_index])
    node.left = constructMaximumBinaryTree(left)
    node.right = constructMaximumBinaryTree(right)
    return node

#
